package leetcode.D2000.T1143;

class Solution {
//    public int longestCommonSubsequence(String text1, String text2) {
//        int[] dp = new int[text1.length()];
//        for(int i=0; i<text2.length(); ++i) {
//            int last = 0;
//            for(int j=0; j<text1.length(); ++j) {
//                if(text2.charAt(i) == text1.charAt(j)) {
//                    if(j == 0) {
//                        last = dp[j];
//                        dp[j] = 1;
//                    } else {
//                        int temp = Math.max(last+1, dp[j-1]);
//                        last = dp[j];
//                        dp[j] = Math.max(temp, dp[j]);
//                    }
//                } else {
//                    last = dp[j];
//                    if(j > 0) {
//                        dp[j] = Math.max(dp[j], dp[j-1]);
//                    }
//                }
//            }
//        }
//        return dp[text1.length()-1];
//    }

    // 二刷
    /*public int longestCommonSubsequence(String text1, String text2) {
        int[] dp = new int[text1.length() + 1];
        for(int i=0; i<text2.length(); ++i) {
            int last = dp[0];
            for(int j=1; j<text1.length()+1; ++j) {
                int temp = text1.charAt(j-1) == text2.charAt(i) ? last+1 : Integer.max(dp[j], dp[j-1]);
                last = dp[j];
                dp[j] = temp;
            }
        }
        return dp[text1.length()];
    }*/

    // 三刷
    public int longestCommonSubsequence(String text1, String text2) {
        int[] dp = new int[text2.length() + 1];
        for (int i=0; i<text1.length(); ++i) {
            int last = dp[0];
            for(int j=1; j<=text2.length(); ++j) {
                int temp = text1.charAt(i) == text2.charAt(j-1) ? last + 1 : Math.max(dp[j-1], dp[j]);
                last = dp[j];
                dp[j] = temp;
            }
        }
        return dp[dp.length-1];
    }
}